1. Field of the Invention
This invention relates generally to the field of Computer Networking and specifically to the field of Routing in Computer Networks.
2. Description of Background Art
A goal of conventional communication systems which convey packetized information is to be able to quickly and efficiently route individual packets of information from the source computer to the destination computer, without undue delay or loss. However, conventional routed networks rely on individual routers to decide the path along which a packet traverses across a network, e.g., a wide area network (WAN). In conventional routed networks, a router collects routing information from its neighboring routers and/or its local manually configured routes. The conventional router does not examine network statistics and routing information for any part of the network that is not directly connected to the router. The router may also gather information on routes that it has been manually configured to implement. Based on this limited local information, the router decides the next router to forward traffic to.
Conventional routers are oblivious to the path taken by a packet beyond the next router. Without being able to calculate the entire path taken by the packet, a router may inadvertently send a packet down a path which may dead-end or may significantly degrade transmission times of the packet to the required destination node.
In addition, conventional routing solutions do not adapt to select an optimal path in the WAN. In addition to the creation of lost or underliverable packets due to a conventional router's poor routing choices, routers may also have different transmission times depending on which router they are sending or receiving data from. Since conventional networks are commonly composed of a variety of different speed lines, it is possible for two separate paths through the WAN to reach the same destination at different times. Based on the local information available to a conventional router, it would be unable to accurately predict which path would reach the intended destination quicker.
These inefficiencies are exacerbated by the realization that the network is not static. The transmission speed of a router may change between an initial time and a subsequent time. Furthermore, a router may need to be taken off-line, removing a potential path as well as removing any manually configured routes. Conventional routers are unable to recognize when a router closer to the required destination has been taken off line or has slowed down significantly. Since it cannot detect disabled routers further downstream, a conventional router would not be able to intelligently choose a different path to avoid the disabled router. As such, the conventional router cannot efficiently choose its route for any given data packet.
What is needed is an efficient method and system for routing information in a dynamic multi-point network which (1) can automatically discover and track changes for an entire meshed overlay network, (2) can verify the existence of optimal routing paths through the meshed overlay network, and (3) can select an optimal routing path through the network based on up-to-date network statistics.